#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        if (nums.size() < 3)return 0;
        sort(nums.begin(), nums.end());
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.size() - 2; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])continue;
            int z = i + 1, y = nums.size() - 1;
            if (nums[i] + nums[i + 1] + nums[i + 1] >= target + abs(ans - target))break;
            while (z < y)
            {
                //cout << nums[i] << " " << nums[z] << " " << nums[y] << endl;
                int temp = nums[i] + nums[z] + nums[y];
                if (abs(temp - target) < abs(ans - target))
                {
                    ans = temp;
                    continue;
                }
                if (temp > target)
                {
                    while (z < y && nums[y] == nums[y - 1])y--;
                    y--;
                }
                else
                {
                    while (z < y && nums[z] == nums[z + 1])z++;
                    z++;
                }
            }

        }
        return ans;
    }
};
int main()
{
    vector<int> nums = { -1,2,3,5,8,9 };
    Solution sol;
    cout << sol.threeSumClosest(nums, 7) << endl;
}